A number of systems and programs are offered on the market for the design, the engineering and the manufacturing of objects. CAD is an acronym for Computer-Aided Design, e.g. it relates to software solutions for designing an object. CAE is an acronym for Computer-Aided Engineering, e.g. it relates to software solutions for simulating the physical behavior of a future product. CAM is an acronym for Computer-Aided Manufacturing, e.g. it relates to software solutions for defining manufacturing processes and operations. In such computer-aided design systems, the graphical user interface plays an important role as regards the efficiency of the technique. These techniques may be embedded within Product Lifecycle Management (PLM) systems. PLM refers to a business strategy that helps companies to share product data, apply common processes, and leverage corporate knowledge for the development of products from conception to the end of their life, across the concept of extended enterprise.
The PLM solutions provided by DASSAULT SYSTEMES (under the trademarks CATIA, ENOVIA and DELMIA) provide an Engineering Hub, which organizes product engineering knowledge, a Manufacturing Hub, which manages manufacturing engineering knowledge, and an Enterprise Hub which enables enterprise integrations and connections into both the Engineering and Manufacturing Hubs. All together the system delivers an open object model linking products, processes, resources to enable dynamic, knowledge-based product creation and decision support that drives optimized product definition, manufacturing preparation, production and service.
Some of these systems allow the representation of a modeled volume with a set of dexels. Several papers or patent documents notably suggest using dexel representation for machining simulation or interactive sculpting.
Examples of such documents are:    the paper entitled “A Virtual Sculpting System Based on Triple Dexel Models with Haptics”, Xiaobo Peng and Weihan Zhang, Computer-Aided Design and Applications, 2009;    the paper entitled “NC Milling Error Assessment and Tool Path Correction”, Yunching Huang and James H. Oliver, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, 1994;    “Online Sculpting and Visualization of Multi-Dexel Volumes”, Heinrich Muller, Tobias Surmann, Marc Stautner, Frank Albersmann, Klaus Weinert, SM '03 Proceedings of the eighth ACM symposium on Solid modeling and applications;    the paper entitled “Virtual prototyping and manufacturing planning by using tri-dexel models and haptic force feedback”, Yongfu Ren, Susana K. Lai-Yuen and Yuan-Shin Lee, Virtual and Physical Prototyping, 2006;    the paper entitled “Simulation of NC machining based on the dexel model: A critical analysis”, Sabine Stifter, The International Journal of Advanced Manufacturing Technology, 1995;    the paper entitled “Real time simulation and visualization of NC milling processes for inhomogeneous materials on low-end graphics hardware”, Konig, A. H. and Grolier, E., Computer Graphics International, 1998. Proceedings;    U.S. Pat. No. 5,710,709; and    U.S. Pat. No. 7,747,418.
GPGPU (General-Purpose computing on Graphics Processing Units) is the technique of using a graphic processing unit (GPU) which typically handles computation only for computer graphics, to perform computation in applications traditionally handled by the central processing unit (CPU). Some papers consider using the computation power of modern graphics processing units (GPU) for dexel representation. These papers make use of the LDNI (Layered Depth-Normal Images) algorithm, which is associated to a specific memory model.
Examples of such papers are:    the paper entitled “GPGPU-based Material Removal Simulation and Cutting Force Estimation”, B. Tukora and T. Szalay, CCP: 94: Proceedings Of The Seventh International Conference On Engineering Computational Technology;    the paper entitled “Layered Depth-Normal Images: a Sparse Implicit Representation of Solid Models”, Charlie C. L. Wang and Yong Chen, Proceedings of ASME international design engineering technical conferences. Brooklyn (N.Y.).
Algorithms for collision detection in general may describe collision in the case of n moving bodies for example. For polygonal representations, many collision detection methods are based on classical geometrical objects such as Binary Space Partitions or Oriented Bounding Volumes. Several algorithms exist for solids represented by CSG. The CSG structure describes a 3D closed solid as the result of a sequence of Boolean operations performed on simple primitives. Finally, solids may be represented by parametric or implicit equations. These representations have led to many algorithms for testing intersection between surfaces, thus detecting collision. These approaches can be gathered into several groups such as analytic method, lattices method, tracing method, implicit equations.
Examples of papers are:    “Collision detection between geometric models: A survey”, Lin, M. and Gottschalk, S., Proc. of IMA Conference on Mathematics of Surfaces, 1998;    “Improvement of collision-detection algorithm based on OBB”, Journal of Huazhong University of Science and Technology, Zhang Qin, Huang Kun, Li Guangming;    “Collision detection and analysis in a physically based simulation”, W. Bouma and G. Vanecek, Proceedings Eurographics workshop on animation and simulation, 1991;    “A new collision detection method for CSG-represented objects in virtual manufacturing”, Chuan-Jun Sub, Fuhua Lina, and LanYeb, Computers in Industry, Volume 40, Issue 1, September 1999, Pages 1-13; and    “Geometric and Solid Modeling”; C. M. Hoffmann, Morgan Kaufmann, San Mateo, Calif., 1989
Collision detection for NC simulation is however specific. The specificity of machining simulation is two folded. On the one hand, the geometry of the workpiece continuously evolves during the machining process. On the other hand, the moving tool includes cutting parts and non-cutting parts, e.g. respectively the shank (the side of the tool) and the holder. In the context of NC machining simulation, or more general sculpting simulation, quite few authors have considered checking the collision between the non-cutting moving parts and the evolving workpiece.
In the following references, the problem of detecting collision problem is addressed by updating the geometry of the part between each collision test:                “Precise global collision detection in multi-axis NC-machining”, Oleg Ilushina, Gershon Elberb, Dan Halperin, Ron Wein, Myung-Soo Kim, Computer-Aided Design 37 (2005) 909-920;        “The sweep plane algorithm for global collision detection with workpiece geometry update for five-axis NC machining”, T. D. Tang, Erik L. J. Bohez, Pisut Koomsap, Computer-Aided Design 39 (2007) 1012-1024; and        Commercial software CAMWorks (registered trademark).        
As can be seen, the history of machining simulation is long. However, the existing solutions lack efficiency, notably from a memory performance point of view, from an accuracy of simulation point of view, and/or from a user utilization point of view.
FIGS. 1-3 illustrate issues that may appear when simulating the machining of a workpiece.
Approaches that only detect collisions at tool positions (this is notably the case of “Precise global collision detection in multi-axis NC-machining”, Oleg Ilushina, Gershon Elberb, Dan Halperin, Ron Wein, Myung-Soo Kim, Computer-Aided Design 37 (2005) 909-920, and CAMWorks) perform a collision detection at each tool position. Consequently, what occurred when the tool moves from one position to the next one is ignored. This implies that a collision occurring between two consecutive positions is ignored. To overcome this flaw, the tool trajectory is usually over-discretized so that the distance between two consecutive tool positions never exceeds a given tolerance. This induces a poor performance since a huge number of checks is required. FIG. 1 illustrates a missed collision between the workpiece 10 and the non-cutting part 12 of the tool 14. FIG. 2 illustrates detection of said missed collision 20 between the workpiece 10 and the non-cutting part 12 of the tool 14, thanks to a good enough discretization. It is noted that such discretization is costly (resulting in a lack of—e.g. visual—fluidity of the simulation), and can never be 100% secure.
Several approaches assume that the workpiece remains constant, meaning that the material removal phenomenon is not handled, which is not realistic when dealing with machining process. These approaches belong to a more general class of algorithms detecting collision between two objects that are supposed not to evolve during time. These algorithms are generally used to solve path planning problems. In the context of machining simulation they are used to check that no collision occurs against the designed part. Only gouge can be detected this way.
Few approaches are able to deal with the two previous problems: these approaches generally aim to consider the workpiece as evolving along time, and allow detecting collisions along tool move and not only at tool positions. However, these approaches can be based on restrictive assumptions about the tool geometry, and they can discard some tools that may require a huge (and even infinite) number of convex parts, such as a torus. These approaches can neither handle tools featuring a void, or round-over tool. More generally, these approaches fail to handle tools resulting from Boolean subtraction between convex parts. Approximating such tools by union of convex parts would result in really poor performance and loss of precision. FIG. 3 illustrates a cutting tool 30 including a non-convex cutting part 32 that is able to machine the workpiece 34 without collision with the non-cutting part 36. As can be seen, no collision should be reported because the shape of the cutting tool and its trajectory ensure that the cutting part always encounters workpiece material first. However, these approaches are likely to wrongly report a collision (although they may be performant from other point of views).
Within this context, there is still a need for an improved solution for simulating the machining of a workpiece.